// #pragma once
#include <iostream>
#include <algorithm>
#include <map>
#include <iomanip>
#include <cstdlib>
#include "AStara.hpp"
#include <float.h>
#include "tinyxml.h"
#include "Graph.h"
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
// #include "GraphFindAllPath_3.hpp"
#include <map>

using namespace std;

#include <assert.h>
#include <algorithm>
using std::sort;
using namespace std;
#define NODE_CNT 50
map<string, Node *> open_list;
int insert_neighbor_to_openlist(Node *curr_node, string _end, map<string, Node> &nodes)
{
	Node *tmp = NULL;
	map<string, Node *>::iterator is_contain;
	for (auto &it : curr_node->endNode)
	{
		tmp = it;
		// is_contain = open_list.find(tmp->nodeType);
		// if (tmp->attr != ATTR_FORBID && tmp->attr != ATTR_CLOSE && is_contain == open_list.end())
		{
			tmp->H = tmp->distance(nodes[_end]);
			tmp->G = curr_node->G + tmp->distance(*curr_node);
			// tmp->G = nodes["s0"].distance(*curr_node);
			tmp->F = tmp->H + tmp->G;
			tmp->parent = curr_node->nodeType;
			open_list[tmp->nodeType] = tmp;
			tmp->print("tmp");
		}
	}

	return 0;
}

static bool comp_f(Nodeas *a, Nodeas *b)
{
	//比较f值
	int a_f = a->g + a->h;
	int b_f = b->g + b->h;
	return a_f < b_f;
}
bool getMinMap(map<string, Node *> &open_list, Node *N)
{
	float minf = FLT_MAX;
	bool ret = false;
	if (open_list.size() > 0)
		for (auto &it : open_list)
		{
			Node *e = it.second;
			cout << e->nodeType;
			if (minf > e->F)
			{
				minf = e->F;
				*N = *e;
				ret = true;
				N->print("MIN");
				// cout << "63h min:" << minf << " n " << N->nodeType << endl;
			}
		}
	else
	{
		cout << "open_list kong" << endl;
	}
	// N->print("minF");
	// cout << "70 find:" << ret << " minf:" << minf << " n:" << N->nodeType << endl;
	return ret;
}

void print_path1(string start, string _end, Node *node, map<string, Node> &nodes)
{
	printf("print path backward order\n");

	// cout << "" << _end;
	vector<string> paths;
	paths.push_back(_end);
	while (node->nodeType != start)
	{
		node->attr = ATTR_RIGHT;
		// cout << "-" << node->parent;
		paths.push_back(node->parent);
		node = &nodes[node->parent];
	}
	cout << "" << endl;
	for (auto it : paths)
	{
		nodes[it].isInPaths = true;
		cout << it << endl;
		// printf("\r\n%d\r\n........",atoi((node->parent.c_str() + 1)));
	}
}
//XML 路径改颜色
int writeXmlColor(string strXmlPath, map<string, Node> &nodes)
{
	TiXmlDocument *writeDoc = new TiXmlDocument; //xml文档指针

	if (!writeDoc->LoadFile(strXmlPath.c_str()))
	{
		cout << "Can not load111 Xml file" << endl;
		cin.get();
		return false;
	}
	TiXmlElement *RootElement = writeDoc->RootElement(); //根元素
	//writeDoc->LinkEndChild(RootElement);
	TiXmlElement *NextElement = RootElement->FirstChildElement();
	srand(time(NULL));

	while (NextElement != NULL)
	{
		if (NextElement->ValueTStr() == "node")
		{
			TiXmlElement *EdgeElement = NextElement->FirstChildElement();

			while (EdgeElement->ValueTStr() != "nodeType")
			{
				EdgeElement = EdgeElement->NextSiblingElement();
			}
			string name = EdgeElement->GetText();

			while (EdgeElement->ValueTStr() != "nodeColor")
			{
				EdgeElement = EdgeElement->NextSiblingElement();
			}

			TiXmlNode *oldnode = EdgeElement->FirstChild();
			char str[128];
			if (nodes[name].isInPaths == true)
			{
				sprintf(str, "%.2f,%.2f,%.2f", 1.0, 0.0, 0.0);
			}
			else
			{
				sprintf(str, "%.2f,%.2f,%.2f", 0.0, 0.0, 1.0);
			}
			TiXmlText newText(str);
			EdgeElement->ReplaceChild(oldnode, newText);
			// cout << EdgeElement->GetText() << endl;
		}
		NextElement = NextElement->NextSiblingElement();
	}

	writeDoc->SaveFile("map_node10_v1.1_color.xml");
	delete writeDoc;

	return 1;
}
void find_destination(string _start, string _end, map<string, Node> &nodes)
{
	Node curr_node;

	if (_start == _end)
	{
		printf("start = end\n");
		return;
	}
	//将起点加入open列表
	open_list[_start] = &nodes[_start];
	curr_node = *open_list[_start];
	// cout << "___" << open_list["s0"].endNode.size() << endl;
	int a = 0;
	cout << "LIST:" << open_list.size() << endl;
	;
	//while (a--)
	while (open_list.size() != 0)
	{
		//拿到open列表中f最小的节点
		if (getMinMap(open_list, &curr_node) == false)
		{
			continue;
		}
		// // //获取节点四周可移动的节点并加入open列表中
		cout << "*********************curr_node*********** " << a++ << endl;
		curr_node = nodes[curr_node.nodeType];
		curr_node.print("curr_node");

		//curr_node.print();

		curr_node.attr = ATTR_CLOSE;
		// curr_node.print();
		if (curr_node.nodeType == _end)
		{
			print_path1(_start, _end, &curr_node, nodes);
			return;
		}
		open_list.clear();
		//cout << curr_node.nodeType << endl;
		insert_neighbor_to_openlist(&curr_node, _end, nodes);

		// open_list.erase(curr_node.nodeType);

		// cout << "LIST:" << open_list.size() << endl;
		// nodes["s1"].print("s1");
		//排序open列表 让f最小的节点放在最前边
	}
	printf("can't find destination\n");
	return;
}

vector<Node> asgraph;
void edge2STATIC(map<string, Node> &nodes, map<string, Edge> &edges)
{
	for (auto &it : edges)
	{

		Edge e = it.second;
		Node *start = &nodes[e.start2end[0]];
		Node *mend = &nodes[e.start2end[1]];
		(nodes[e.start2end[0]].endNode).push_back(mend);
	}
	for (auto &it : nodes)
	{
		cout << "" << it.second.nodeType << endl;
		for (auto &ait : it.second.endNode)
		{
			cout << "" << ait->nodeType << ",";
		}
		cout << endl;
	}
}
#include <ctime>
//44055 :1s49-s25-s22-s43-s32-s30-s29-s6-s3-s1-s0:
int main()
{
	clock_t startTime, endTime;
	startTime = clock(); //计时开始
	//初始化map_next
	map<string, Edge> edges;
	vector<Graph> graph;
	map<string, Node> nodes;
	vector<vector<Node>> paths;
	vector<double> diss;
	vector<double> times;
	bool result;
	int nodeNum = 0;
	int edgeNum = 0;

	result = readXml("map_node50_v1.1.xml", nodes, edges, nodeNum, edgeNum);
	if (result)
	{
		//generateGraph(nodes, edges, graph, nodeNum, edgeNum);
	}

	int cntnum = 0;
	printf("nodes.size:%d\r\n", nodeNum);
	printf("edges.size:%d\r\n", edgeNum);

	edge2STATIC(nodes, edges);

	find_destination("s0", "s49", nodes);
	// writeXmlColor("map_node50_v1.1.xml", nodes);
	endTime = clock(); //计时结束
	cout << "The run time is: " << (double)(endTime - startTime) / CLOCKS_PER_SEC << "s" << endl;
	return 0;
}
